#define _CRT_SECURE_NO_WARNINGS 1
//一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。
//编写一个函数找出这两个只出现一次的数字。
//例如：
//有数组的元素是：1，2，3，4，5，1，2，3，4，6
//只有5和6只出现1次，要找出5和6

#include<stdio.h>
//思路
//所有元素按位异或
//最后结果相当于两个单身狗异或
//101
//110
//011结果中，为1的，代表该位单身狗不相同，一个为1，一个为0
//把元素按该位为1的分为一组，该位为0的分为一组，两个单身狗分开的同时，每组也能内部配对成功

void find_single_dog(int arr[], int sz)
{
	int single1 = 0;
	int single2 = 0;
	int i;
	int tmp = 0;
	//所有元素异或
	for (i = 0; i < sz; i++)
	{
		tmp = arr[i] ^ tmp;
	}
	//寻找分组条件，即从低位数第一个为1的二进制位
	int pos = 0;
	for (i = 0; i < 32; i++)
	{
		if ((tmp >> i) & 1 == 1)
		{
			pos = i;//第i+1位为1
			break;
		}
	}
	//分组异或
	for (i = 0; i < sz; i++)
	{
		if ((arr[i] >> pos) & 1 == 1)
		{
			single1 = arr[i] ^ single1;
		}
	}
	single2 = tmp ^ single1;
	printf("%d %d", single1, single2);
	return;

	//可以但麻烦
	//for (i = 0; i < sz; i++)
	//{
	//	if ((arr[i] >> pos) & 1 == 0)
	//	{
	//		single2 = arr[i] ^ single2;
	//	}
	//}
}
int main()
{
	int arr[] = { 1,2,3,4,5,1,2,3,4,6 };
	int sz = sizeof(arr) / sizeof(int);
	find_single_dog(arr, sz);
	return 0;
}